package class06_quickSortRelated;

public class HollandFlag {
    public static void sortColors(int[] nums) {
        int pIndex = 0;
        int left_bound_1 = 0;

        //找1在不在
        int i = 0;
        while(i<nums.length && nums[i]!= 1){
            i++;
        }

        if(i < nums.length){//存在1
            swap(nums, 0, i);
            left_bound_1=partition(nums,0,nums.length-1);
        }

        //找2在不在
        pIndex=0;
        i = 0;
        while(i<nums.length && nums[i]!=2){
            i++;
        }
        if(i<nums.length){//存在2
            swap(nums, left_bound_1, i);
            partition(nums, left_bound_1, nums.length-1);
        }
    }

    public static void swap(int[] arr, int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

//    public static int partition(int[] nums, int l, int r){
//        int pIndex = l;
//        int q = r;
//
//        while(q!=pIndex){
//
//            while(nums[pIndex]<=nums[q]&&q>pIndex){q--;}
//
//            if(q>pIndex){
//                swap(nums,pIndex,q);
//                int temp;
//                temp = pIndex; pIndex = q; q = temp;
//                q++;
//            }
//
//            while(nums[q]<nums[pIndex]&&q<pIndex){q++;} //左边要摘干净所以用<
//            if(q<pIndex){
//                swap(nums,pIndex,q);
//                int temp;
//                temp = pIndex; pIndex = q; q = temp;
//                q--;
//            }
//        }
//        return pIndex;
//    }
    public static int partition(int[] nums, int l, int r){
        int i = l;
        int j = r;
        while(j>i){
            while(j>i && nums[i]<=nums[j])j--;
            if(j>i){
                swap(nums,i,j);
                i++;
            }else break;

            while(j>i && nums[i]<=nums[j])i++;
            if(j>i){
                swap(nums,i,j);
                j--;
            }else break;
        }
        return j;
    }


    public static void main(String[] args) {
        int[] arr = {0,1,2,1,2,0,1,2,1,0};
        for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
        System.out.println();
        sortColors(arr);
        for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
    }
}
